package com.easy.carl.algorithm.array.slidingWindow;

import jdk.internal.org.objectweb.asm.Handle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName MinWindow76
 * @Description 76. 最小覆盖子串
 * @Author zheng
 * @Date 2021/12/15 16:35
 * @Version 1.0
 **/
public class MinWindow76 {
    public String minWindow1(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        //最小值
        int minLen = Integer.MAX_VALUE;
        //结果
        String res = "";
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < s.length(); i++) {
            Map<Character, Integer> tmp = new HashMap<>(map);
            if (!tmp.containsKey(s.charAt(i))) {
                continue;
            }
            for (int j = i; j < s.length(); j++) {
                Character sChar = s.charAt(j);
                int num = tmp.getOrDefault(sChar, 0);
                if (num > 1) {
                    tmp.put(sChar, num - 1);
                } else {
                    tmp.remove(sChar);
                }
                if (tmp.isEmpty()) {
                    if (j - i + 1 < minLen) {
                        minLen = j - i + 1;
                        res = s.substring(i, j + 1);
                    }
                    break;
                }
            }
        }
        return res;
    }

    public String minWindow(String s, String t) {
        //肯定不符合条件
        if (s.length() < t.length()) {
            return "";
        }
        //字符串t中每个字符的个数
        Map<Character, Integer> map = new HashMap<>();
        //左指针，右指针
        int left = 0, right = 0;
        //字符串s左右指针之间的字符，且存在于字符串t中的字符
        Map<Character, Integer> leftMap = new HashMap<>();
        //最小值
        int minLen = Integer.MAX_VALUE;

        int leftAns = 0, rightAns = 0;
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> tmp = new HashMap<>(map);
        while (right < s.length()) {
            //右指针对应的字符
            char rightChar = s.charAt(right);
            int count = tmp.getOrDefault(rightChar, 0);
            if (count > 1) {
                tmp.put(rightChar, --count);
            } else {
                tmp.remove(rightChar);
            }
            if (map.containsKey(rightChar)) {
                leftMap.put(rightChar, leftMap.getOrDefault(rightChar, 0) + 1);
            }
            //指针右移
            right++;
            //当前指针位置已包含t中所有的字符，尝试开始收缩左边界
            while (tmp.isEmpty()) {
                //System.out.println(s.substring(left, right));
                //记录比当前字符串短的字符串
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                    leftAns=left;
                    rightAns=right;
                }
                //收缩左边界
                char leftChar = s.charAt(left);
                //两个指针之间的字符个数，少于t中对应字符的个数，说明左指针移过了，需要重新移动右指针
                if (map.containsKey(leftChar)) {
                    if (leftMap.get(leftChar) - 1 < map.get(leftChar)) {
                        tmp.put(leftChar, 1);
                    }
                    leftMap.put(leftChar, leftMap.get(leftChar) - 1);
                }
                //左指针右移一位
                left++;
            }
        }
        return s.substring(leftAns,rightAns);
    }

    public static void main(String[] args) {
        MinWindow76 minWindow76 = new MinWindow76();
        System.out.println(minWindow76.minWindow("ADOBECODEBANC", "ABC"));
    }
}
